package com.mccken.practice.top100.Top_1$20.top_7;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-01 18:56
 **/
public class LengthOfLongestSubstring {

	/*
	滑动窗口算法，用一个map记录窗口

	1. 什么时候增加窗口？ -> 遇到的字符不在子串中
	2. 什么时候收缩窗口？ -> 遇到了重复子串
	3. 增加窗口后，要做啥？ -> right++，res++；
	4. 收缩窗口后，要做啥？ ->    left--，res重新记录 	
	
	
	 */
	public int lengthOfLongestSubstring(String s) {
		if (s.isEmpty()) {
			return 0;
		}

		int left = 0, right = 0, res = 0;
		Set<Character> window = new HashSet<>();

		while (right < s.length()) {
			char rightC = s.charAt(right);
			boolean flag = window.add(rightC);

			right++;

//			System.out.println(window);

		
		    if (!flag) {
				while (true) {
					char leftC = s.charAt(left);
					left++;	
					if (leftC == rightC) {
						break;
					}
					window.remove(leftC);
				}
		    }
			
			res = Math.max(res, right - left);
		}

		return res;

	}

	public int lengthOfLongestSubstring1(String s) {
		if (s.isEmpty()) {
			return 0;
		}

		int left = 0, right = 0, res = 0;
		HashMap<Character, Integer> window = new HashMap<>();

		while (right < s.length()) {
			char rightC = s.charAt(right);
			Integer rightC_count = window.get(rightC);
			if (rightC_count == null) {
				rightC_count = 1;
			} else {
				rightC_count++;
			}
			window.put(rightC, rightC_count);

			right++;

			while (window.get(rightC) > 1) {
				char leftC = s.charAt(left);
				Integer leftC_count = window.get(leftC);
				window.put(leftC, --leftC_count);
				left++;
			}

			res = Math.max(res, right - left);
		}

		return res;

	}

	public static void main(String[] args) {
		LengthOfLongestSubstring l = new LengthOfLongestSubstring();
		System.out.println(l.lengthOfLongestSubstring("abcabcbb"));
		System.out.println(l.lengthOfLongestSubstring("bbbbb"));
		System.out.println(l.lengthOfLongestSubstring("pwwkew"));
		System.out.println(l.lengthOfLongestSubstring("tmmzuxt"));
	}
}
